#include<stdio.h>
#include<stdlib.h>
 struct Node {
      int val;
      struct Node *next;
      struct Node *random;
 };
 
typedef struct Node Node;
Node* buyNode (int x)
{
    Node*node = (Node*)malloc(sizeof(Node));
    node->val = x;
    node->random=node->next=NULL;
    return node;
}
void AddNode(Node*head)
{
    Node*pcur = head;
    while(pcur)
    {
        Node*next = pcur->next;
        Node*newnode= buyNode(pcur->val);
        newnode->next = next;
        pcur->next = newnode;
        pcur = next; 
    }
}
void SetRandom(Node*head)
{
    Node*pcur = head;
    
    while(pcur)
    {
        Node*copy = pcur->next;
        if(pcur->random)
        {
            copy->random= pcur->random->next;
        }
        pcur = copy->next;
    }
}
struct Node* copyRandomList(struct Node* head)
{
    if(head == NULL)
    {
        return head;
    }
	AddNode(head);
    SetRandom(head);
    Node*pcur = head;
    Node*newHead,*newTail;
    newHead = newTail = pcur->next;
    while(newTail->next)
    {
        pcur = newTail->next;
        newTail ->next =pcur->next;
        newTail = newTail->next;
    }
   return newHead;
}